/*************************************************************************
 * File Name:    Largest_Rectangle_in_Histogram.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/8 0:25:18
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Largest Rectangle in Histogram
 |
 | Given n non-negative integers representing the histogram's bar height where
 | the width of each bar is 1, find the area of largest rectangle in the histogram.
 |
 | Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
 |
 | The largest rectangle is shown in the shaded area, which has area = 10 unit.
 |
 | For example,
 | Given height = [2,1,5,6,2,3],
 | return 10.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    int largestRectangleArea(vector<int> &height)
    {
        int N = height.size();
        vector<int> width(N, 0);
        
        stack<int> s;
        for (int i = 0; i < N; ++i) {
            while (!s.empty() && height[s.top()] >= height[i]) {
                s.pop();
            }
            if (s.empty()) width[i] = i + 1;
            else width[i] = i - s.top();
            s.push(i);
        }
        while (!s.empty()) s.pop();
        for (int i = N - 1; i >= 0; --i) {
            while (!s.empty() && height[s.top()] >= height[i]) {
                s.pop();
            }
            if (s.empty()) width[i] += N - 1 - i;
            else width[i] += s.top() - i - 1;
            s.push(i);
        }
        int ans = 0;
        for (int i = 0; i < N; ++i) {
            ans = max(ans, width[i] * height[i]);
        }
        return ans;
    }
};

